package Data_Structure.Sort;


/**
 * @className: MergeSort
 * @author: 芃
 * @description: 归并排序实现
 * @date: 2023/8/20 17:19
 */
//主要思想：
//将一个数组逐渐划分为多个小数组，小数组的最小容量为1
//划分完成后，分别将这N多个小数组进行合并，在最小容量为1时，我们可以认为数组为有序的
//合并完成后单个数组容量逐渐增大，反复合并
//当单个数组容量逐渐恢复到原有数组大小时，此时数组就已经有序了
//
//时间复杂度：O(N*logN)
//空间复杂度：数组分割时会大量开辟额外空间进行存储 O(N)
//稳定性：稳定的 可以实现为不稳定的，两个数组元素比较的时候去掉等号即可
public class MergeSort {
    //非递归实现
    //每组从1个数据-》2个数据-》四个数据
    public static void mergeSort2(int[] arr){
        int gap = 1;//每组的数据个数
        while (gap < arr.length){
            //数组每次都要重新进行遍历
            for (int i = 0; i < arr.length; i += 2*gap) {
                int left = i;
                int mid = left + gap - 1;
                //防止越界
                if (mid >= arr.length){
                    mid = arr.length - 1;
                }
                int right = mid + gap;
                //防止越界
                if (right >= arr.length){
                    right = arr.length - 1;
                }
                mergeArr(arr,left,mid,right);
            }
            gap *= 2;
        }
    }
    //递归实现
    public static void mergeSort(int[] arr){
        mergeSortInternal(arr,0,arr.length - 1);
    }
    private static void mergeSortInternal(int[] array,int low,int high){
        if (low >= high){
            return;
        }
        int mid = low + ((high - low) >>> 1);
        //左边
        mergeSortInternal(array,low,mid);
        //右边
        mergeSortInternal(array,mid + 1,high);
        //合并
        mergeArr(array,low,mid,high);
    }
    private static void mergeArr(int[] arr,int low,int mid,int high){
        int s1 = low;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = high;
        int[] tmp = new int[high - low + 1];
        int k = 0;
        while (s1 <= e1 && s2 <= e2){
            if (arr[s1] <= arr[s2]){
                tmp[k++] = arr[s1++];
            }else {
                tmp[k++] = arr[s2++];
            }
        }
        while (s1 <= e1){
            tmp[k++] = arr[s1++];
        }
        while (s2 <= e2){
            tmp[k++] = arr[s2++];
        }
        //拷贝tmp数组的元素，放入原来的arr数组当中
        int index = 0;
        for (int i = low; i <= high; i++) {
            arr[i] = tmp[index++];
        }
    }
    //两个有序数组合并为一个有序数组
    public static int[] merge(int[] nums1, int[] nums2) {
        int index = 0;
        int index1 = 0;
        int index2 = 0;
        int[] ret = new int[nums1.length + nums2.length];
        while (index1 < nums1.length && index2 < nums2.length){
            if (nums1[index1] < nums2[index2]){
                ret[index] = nums1[index1];
                index1++;
            }else {
                ret[index] = nums2[index2];
                index2++;
            }
            index++;
        }
        if (index1 == nums1.length){
            for (int i = index2; i < nums2.length; i++) {
                ret[index] = nums2[i];
                index++;
            }
        }else if (index2 == nums2.length){
            for (int i = index1; i < nums1.length; i++) {
                ret[index] = nums1[i];
                index++;
            }
        }
        return ret;
    }
}
